The invention relates generally to wireless communications. More particularly the present invention is a protocol for use with ad hoc mobile networks that distributively controls medium access thereby avoiding collisions of communications and providing quality of service in a synchronous communications system.
Ad hoc mobile networks have been proposed as a solution to wireless networking where nodes are mobile, the range of their mobility exceeds the transmission range of any single transceiver, and there is no existing network infrastructure such as that which exists in a more traditional fixed wireless network having transmission towers and base stations. Typical proposed applications for such ad hoc networks include military command and control, search and rescue, sensor, and disaster relief networks. However, ad hoc networking may find broader application as a networking approach in offices, across college campuses, in homes, and even possibly as the architecture of a future generation of mobile wireless data networks. Indeed, the increasing availability of high frequency transceivers (i.e. high bandwidth) will allow simultaneous support of multiple connections at different qualities of service (QoS). However, the increased attenuation associated with such high frequencies will make cellular architectures centered on nodes communicating directly with base stations impractical. The natural alternative is for nodes to communicate with their peers rather than with a base station and to cooperate to support connectivity as is envisaged by the ad hoc networking approach.
Ad hoc networks have no base stations and are quite volatile. The performance of these networks is contingent on the ability of access protocols to allocate bandwidth and the ability of routing protocols to determine and to maintain routes among the nodes. Extensive research has been directed toward this issue and numerous protocols have been proposed for medium access.
Three major challenges confront ad hoc access protocols: providing fair access onto a single channel to multiple contending nodes (i.e. all contending nodes have the same opportunity to gain access), achieving spatial reuse of the channel, and providing a mechanism that allows nodes to reserve bandwidth on the single access channel.
Fair access is typically achieved either by scheduling accesses or by introducing temporal randomness so that nodes may gain access at different times. Due to the distributed nature of ad hoc networks, temporally random access techniques improving on the principles underlying the Aloha and Carrier Sense Multiple Access (CSMA) protocols have dominated.
The IEEE 802.11 and the ETSI HIPERLAN MAC protocols exemplify the state of the art in standardized protocols. The 802.11 MAC is based on a distributed CSMA like protocol that seeks to avoid collisions when the channel is congested. Nodes schedule packet transmissions to start in randomly selected time slots within a contention window. Nodes transmit the packets after sensing the channel to be idle for that selected number of time slots. If the packet is not received successfully, a back off algorithm randomly schedules retransmission in a larger contention window. The contention window increases exponentially with each failure, thus reducing the probability that nodes, which collide, will subsequently collide. However, the protocol's performance still degrades with congestion.
The HIPERLAN protocol takes a different approach. Nodes first attempt to send packets as they arrive. If a packet arrives when the channel is busy, the node waits until the channel is free again and then contends immediately using the signaling protocol Elimination Yield Non-Preemptive Multiple Access (EYNPMA). When multiple nodes within range of each other contend simultaneously, this protocol is better than 96% effective at isolating a single winner. By contrast with 802.11, the performance of this access mechanism is robust. However, as the density of nodes increases, so does the susceptibility of the protocol to hidden node effects. This susceptibility occurs because the timing of EYNPMA is based on the release of the channel by a transmitter. Only nodes within range of this transmitter can achieve the appropriate synchronization.
RICH-DP offers a variation to slotted Aloha. All nodes follow a common frequency hopping sequence. Access attempts occur on these hops as in slotted aloha but they are receiver initiated. Nodes poll their peers in these hops to determine if their peer has a packet to send them. If so, the two nodes exchange data stalling at that hop frequency and thereby avoiding collisions with future polls and data exchanges, which will occur on other hop frequencies. The use of request-to-receive (RTR) messages sent by destinations results in collision avoidance as collisions occur at destinations. Unique to this approach is that not only do the access attempts occur at random times, they may occur when the sources have no data to send. Nevertheless on account of a dedicated collision free channel for the subsequent data exchange and the concurrent use of multiple channels in the same space it is a very competitive protocol. Its limitations are that it is sensitive to high node densities on account of the finite number of frequencies and (typical of the slotted aloha access mechanism) is subject to congestion collapse as collisions may still occur in the RTR polls.
The dispersion of nodes in networks offers the potential to spatially reuse the radio channel so that more than one pair of nodes can exchange data at a time but also results in the pesky hidden node phenomena where distant nodes transmitting simultaneously unbeknownst to each other interfere at one or both destinations. The challenge to access protocols is to resolve from a spatial distribution of transmitters a set that can use the channel simultaneously without interfering with each other.
The deleterious impact of the hidden node problem is a significant issue for CSMA protocols. In fact, when “wireless” CSMA was first presented, it was noted that CSMA's performance could degrade to that of Aloha. Subsequently, it was demonstrated that a two-way handshake prior to data transmission could suppress collisions. The principle is for the source to first transmit a short “request-to-send” (RTS) packet to the destination implicitly directing all nodes within range to back off while the data exchange takes place. Upon receiving the RTS, the destination replies with a “clear-to-send” (CTS) packet, which simultaneously directs its neighbors to back off while giving the source the go-ahead to transmit the data packet. Collisions may still occur during RTS-CTS exchanges but they only interfere with these short transmissions rather than the longer data transmissions. In fact, modeling of the present invention demonstrates that a successful RTS-CTS exchange is a sufficient condition to assure no collision in the subsequent data transmission.
The RTS-CTS exchanges are currently used by 802.11. By contrast, HIPERLAN takes a different approach in dealing with hidden nodes. A node assumes a collision has occurred when it fails to gain access but then does not detect a packet transmission. When this is the case the node identifies this as the “hidden elimination” condition and foregoes attempting to gain access for at least 500 ms. Unfortunately, various studies reveal HIPERLAN's performance degrades significantly with an increase of hidden nodes.
RICH-DP avoids the channel sharing challenge by segregating transmissions on different frequencies.
Access protocols must enable the reservation of resources if they are to achieve bandwidth or delay QoS constraints.
The 802.11 protocol supports two types of coordination functions built upon its distributed access mechanisms, a distributed coordination function (DCF) and a point coordination function (PCF). The DCF is the default. The PCF enables a central node, the point coordinator (PC), to schedule transmissions; however, the standard provides no guidance on how this should be done. The PCF can be used to support multimedia traffic in certain situations, but this assumes that all nodes are within range of the PC. In a widely distributed network, this approach would require multiple PCs working together to manage access. Currently no work attempting such a solution for an ad hoc network appears to exist. In fact, the DCF remains the predominant coordination function used in ad hoc networking. Attempts have been made to add signaling to the DCF so as to enable it to support constant bit rate services; however, this work again requires all nodes to be within range of each other. The 802.11 protocol does not simultaneously support resource reservation and spatial reuse.
HIPERLAN's method of supporting QoS is to give priority to packets based on their residual lifetime. The EYNPMA protocol has five levels of priority, all based on the residual lifetime of a packet. Unfortunately, experiments demonstrate that this priority scheme is not effective at supporting QoS since there are no mechanisms to distinguish between packets associated with real time services and old data packets. The problem is, of course, more pronounced in congested networks where more nodes would contend to transmit old, i.e. higher priority, data packets.
Spread spectrum (SS) technology has frequently been proposed as a method to multiplex signals within the same geographic region. Spread spectrum also offers other very attractive features such as resistance to detection, resistance to multipath induced fades, and resistance to jamming. Multiple transmissions can coexist in the same frequency band when using orthogonal spread spectrum codes. This is a key technology in cellular phone systems and is the basis of code division multiple access (CDMA).
Unfortunately, several complications are introduced by the distributed nature of ad hoc networks. First, the question arises, “which code to use and when to use it?” Synchronizing the codes transmitters use to those that receivers are using to receive is not trivial. Second, in a channel with only a finite number of codes available, the network needs to assign codes such that they are spatially distributed. In a dynamic network, keeping track of codes can be as complicated as keeping track of routes. Third, unlike CDMA cell phone systems, it is possible that a destination will be closer to an interfering transmitter than its source transmitter.
Even with a different spreading sequence the relative power of the interfering signals can raise the effective noise level of the channel such that the desired signal is lost. Finally, when codes are used, networks become packet sensing as opposed to carrier sensing. Receivers must synchronize with the transmitter from the beginning of the packet transmission or else the transmission appears as noise. To avoid interfering with an ongoing exchange at a destination a source must know that the destination is idle and is ready to receive its transmission. The only way to be certain that the destination is idle is to monitor the exchanges to and from the destination. This is difficult, since it may be impossible to monitor an incoming transmission to this destination on account of separation from the distant source. Not knowing who this source is also prevents knowing the code that would be used in the destination's acknowledgement. Not sensing a destination is busy is no guarantee that it is idle.
There are four approaches to selecting codes: transmitter-based, receiver-based, pair-wise oriented, and common code shifted in time. In transmitter-based schemes a unique code is assigned to each transmitter. The problem with this approach is determining which transmitter's code a potential receiver should use at a given time.
In receiver-based schemes a unique code is assigned to each receiver. In this approach, there is no confusion at either the receiver or the transmitter as to which code to use but there is the question as to when the transmitter should start transmitting. Transmitting to a destination that is already receiving a packet from another source can interfere with that reception.
With transmitter-based codes the problem associated with an adjacent node interfering with a destination's reception is not as severe since it is precluded from using the same code.
In pair-wise oriented schemes unique codes are assigned to pairs of nodes. Pair-wise coding presents the same challenge to destinations as transmitter-based codes. Each potential destination needs to determine which code it should use in receiving.
Common code systems rely on the offset of the phase of codes used in transmissions that occur concurrently. The offsets may either occur randomly or be deliberate. In the latter case, the selection of the offset is no different than the selection of the spread spectrum code in the first three approaches. Additionally, despite the presence of an offset when using common codes there is still an increased likelihood that signals may interfere with each other. However, using a common code has an advantage in that it is the only approach that can support broadcast transmissions.
Proposed solutions to the problem of selecting codes normally involve the use of hybrid protocols. In one hybrid, all nodes monitor and contend using a common code but after the addresses of the source and destination are transmitted the transmitter uses a transmitter-based code to send the data packet. The destination knows which code to use since it receives the source address before the transition to the use of the transmitter-based code. In a second protocol, every node is assigned two codes, one to receive on and one to transmit on. When a node is idle it listens using its receive code. A source will use the receive code of the destination of a packet to send the source and destination address portion of the packet but will again transition to the source's transmit code to send the data portion.
Both approaches attempt to limit the time that another node may interfere with the exchange. In the first, other nodes will only interfere during the initial transmission of the addresses and in the second the potential interference occurs during the same period but is further reduced on account that interfering nodes must be transmitting to the same destination. The disadvantage of the second protocol over the first is its inability to broadcast packets.
The assignment of codes is also a problem in spread spectrum ad hoc networks. Normally there are a finite number of codes that must be distributed to a larger number of nodes. Random selection of codes may not assure the required physical separation of nodes using the same codes. Various algorithms have been developed for the assignment of codes. Most methods of assigning and distributing codes are associated with the hierarchical organization of networks.
Code assignment does not eliminate the unwanted interference from transmitters in close proximity to the destination end of other exchanges. In other words, the interfering source is closer to a destination than its intended source. Ideally, an access protocol would deliberately select transmitting nodes that do not interfere at the destinations.
Although there has been much work on the use of spread spectrum in ad hoc networks there are no protocols that completely integrate within a medium access control protocol the assignment of codes, the scheduling of a spatially distributed set of transmissions, and a method used by nodes to select codes for transmission and reception. In turn there are no methods that support the use of CDMA technology to transmit different messages from one node to many.
Mobile nodes in ad hoc networks frequently rely on batteries for energy and therefore have a finite lifetime. Conserving energy is therefore important to extending the lifetime of both individual nodes and the network. This is especially difficult in ad hoc networks since energy conserving actions must be made in a distributed manner. In fact, the continuous participation of the mobile nodes to create a fabric of connectivity is critical to the overall performance of the network. Typically, this results in a choice of either operating at peak performance at the expense of a shortly lived network or choosing sub optimum performance for network longevity. Additionally, most energy conserving protocols focus on the implementation of a single energy conserving approach.
Protocols may use four sets of mechanisms to reduce energy consumption: 1) help nodes enter low energy states; 2) choose routes that consume the least energy; 3) selectively use nodes based on their energy status; 4) reduce overhead.
Access protocols reduce energy consumption by coordinating the use of low energy states. Using low energy states has great potential for conserving energy since these state use less than a tenth of the energy used by radios when receiving or transmitting. The default state of nodes is receiving since signal processing is required to detect and to synchronize to an incoming signal. Entering a low energy state requires the node to cease sensing the channel and to stop participating in the network's activities. The objective of type 1 energy conserving protocols is to assist nodes that are not participating in data exchanges to enter a low energy state without degrading overall performance of the network. Proposed methods for managing nodes entering the doze state may be one of two kinds. In the first, nodes doze and then wakeup on a periodic basis according to network wide parameters. The 802.11 standard provides this kind of mechanism. The second requires the node desiring to doze to specifically coordinate a dozing cycle with another supporting node that agrees to act as a surrogate destination for the dozing node's traffic while it is dozing. The ETSI HIPERLAN standard uses this approach.
In both the 802.11 and HIPERLAN protocols, the decision to doze is initiated by the individual nodes desiring to conserve energy. In the ad hoc version of an 802.11 network, the node that first forms the network decides whether it permits energy conservation by establishing an “ATIM Period.” A node that desires to conserve energy may doze so long as it wakes each ATIM Period to listen for ad hoc traffic indication messages (ATIM). ATIMs are transmitted during a short window at the beginning of each ATIM period, called an ATIM Window. If the node wakes and hears an ATIM directed to itself, it acknowledges the ATIM and remains awake for the rest of the ATIM period prepared to receive traffic. If it receives no ATIM directed to itself, the node returns to the doze state at the conclusion of the ATIM window. Note that there is no method for a node's intent to doze to be disseminated. Other nodes assume this state after failing to transfer data through regular contention.
The energy conserving mechanism in HIPERLAN requires a node desiring to doze, a “p-saver,” to coordinate with another to serve as its surrogate, a “p-supporter”. As part of this coordination the two nodes agree to a period at which the p-saver will awaken to receive unicast messages and a period at which the p-supporter will transmit multicast messages. The p-supporter node collects transmissions intended for the p-saver and then attempts to forward them to the p-saver during the coordinated transmission periods.
The critical deficiency of both the 802.11 and HIPERLAN techniques is that they do not account for the repercussions of a single node's decision to enter the doze state. These repercussions are more congestion as nodes attempt to send traffic to nodes that are dozing and complications for other protocols higher in the stack such as routing. To minimize these adverse effects, access protocols must be able to make dozing more predictable.
In view of the above, what would be truly useful is an access protocol that can be used with wireless ad hoc networks. Such a protocol would arbitrate medium access such that it provides quality of service, manages the use of low energy states, coordinates the use of multiple channels, all while allowing maximum use of wireless channels minimizing collisions of concurrent communications.